/**
 * 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 */

function bubbleSort1(arr) {
  console.time("经典冒泡排序耗时");
  let length = arr.length - 1;
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // let temp = arr[j + 1];
        // arr[j + 1] = arr[j];
        // arr[j] = temp;
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
      }
    }
  }
  console.timeEnd("经典冒泡排序耗时");
  return arr;
}

function bubbleSort2(arr) {
  console.time("改进后冒泡排序耗时");
  var i = arr.length - 1; //初始时,最后位置保持不变
  while (i > 0) {
    var pos = 0; //每趟开始时,无记录交换
    for (var j = 0; j < i; j++)
      if (arr[j] > arr[j + 1]) {
        pos = j; //记录交换的位置
        // var tmp = arr[j];
        // arr[j] = arr[j + 1];
        // arr[j + 1] = tmp;
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
      }
    i = pos; //为下一趟排序作准备
  }
  console.timeEnd("改进后冒泡排序耗时");
  return arr;
}

function bubbleSort3(arr3) {
  var low = 0;
  var high = arr.length - 1; //设置变量的初始值
  var tmp, j;
  console.time("2.改进后冒泡排序耗时");
  while (low < high) {
    for (
      j = low;
      j < high;
      ++j //正向冒泡,找到最大者
    )
      if (arr[j] > arr[j + 1]) {
        tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    --high; //修改high值, 前移一位
    for (
      j = high;
      j > low;
      --j //反向冒泡,找到最小者
    )
      if (arr[j] < arr[j - 1]) {
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
      }
    ++low; //修改low值,后移一位
  }
  console.timeEnd("2.改进后冒泡排序耗时");
  return arr3;
}

function bullleSort4(arr4) {
  console.time("3.改进后冒泡排序耗时");
  for (var i = 0; i < arr4.length - 1; i++) {
    let complete = true;
    for (var j = 0; j < arr4.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        complete = false;
      }
    }
    if (complete) {
      break;
    }
  }
  console.timeEnd("3.改进后冒泡排序耗时");
  return arr4;
}

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort1(arr));
console.log(bubbleSort2(arr));
console.log(bubbleSort3(arr));
console.log(bullleSort4(arr));
